import java.util.ArrayList;
import java.util.List;

/**
 * Created by asus on 2018/7/4.
 * 快排
 */
public class quickSort {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(56);
        arrayList.add(87);
        arrayList.add(44);
        arrayList.add(2);
        arrayList.add(87);
        arrayList.add(55);
        arrayList.add(36);
        arrayList.add(33);
        arrayList.add(93);
        arrayList.add(25);
        arrayList.add(7);
        arrayList.add(67);
        List<Integer> end = quick(arrayList);
        for (Integer e : end) {
            System.out.println(e);
        }
    }

    public static List<Integer> quick(List<Integer> array){
        if (array.size() < 2){
            return array;
        }
        Integer a = array.get(0);
        List<Integer> less = new ArrayList<>();
        List<Integer> more = new ArrayList<>();

        for (Integer i : array) {
            if (i < a) {
                less.add(i);
            } else if (i > a){
                more.add(i);
            }
        }
        List<Integer> l =  quick(less);
        List<Integer> m =  quick(more);
        l.add(a);
        l.addAll(m);
        return l;
    }
}
